//
// Created by PC on 2024/9/2
//


#include <iostream>
#include "arrUtil.h"

using namespace std;

// 分成小于等于区和大于区 以第一个数为基准
int part(int *a, int l, int r)
{
    int le = l;
    int v = a[l];
    for (int i = l+1; i <= r ; ++i)
    {
        if (a[i]<=v)
        {
            le++;
            swap(a[le],a[i]);
        }
    }
    swap(a[le],a[l]);
    return le;
}

void quickSort(int * a , int l, int r)
{
    if(l<=r)
    {
        int m = part(a,l,r);
        quickSort(a,l,m-1);
        quickSort(a,m+1,r);
    }
}
    int main()
    {
//        int arr[]{7, 9, 8, 7, 4, 3, 3, 6};
//        int n = 8;
//        cout << part(arr, 0, n-1) << endl;
//        printArr(arr,n);
        
        int n = 1000;
        int arr[1000];
        randomArr(arr, n);

        quickSort(arr,0, n - 1);
        printArr(arr, n);
        cout << checkSort(arr, n);
        return 0;
    }